//<p>给你一个字符串 <code>s</code> 、一个字符串 <code>t</code> 。返回 <code>s</code> 中涵盖 <code>t</code> 所有字符的最小子串。如果 <code>s</code> 中不存在涵盖 <code>t</code> 所有字符的子串，则返回空字符串 <code>""</code> 。</p>
//
//<p> </p>
//
//<p><strong>注意：</strong></p>
//
//<ul>
//	<li>对于 <code>t</code> 中重复字符，我们寻找的子字符串中该字符数量必须不少于 <code>t</code> 中该字符数量。</li>
//	<li>如果 <code>s</code> 中存在这样的子串，我们保证它是唯一的答案。</li>
//</ul>
//
//<p> </p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = "ADOBECODEBANC", t = "ABC"
//<strong>输出：</strong>"BANC"
//</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>s = "a", t = "a"
//<strong>输出：</strong>"a"
//</pre>
//
//<p><strong>示例 3:</strong></p>
//
//<pre>
//<strong>输入:</strong> s = "a", t = "aa"
//<strong>输出:</strong> ""
//<strong>解释:</strong> t 中两个字符 'a' 均应包含在 s 的子串中，
//因此没有符合条件的子字符串，返回空字符串。</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>1 <= s.length, t.length <= 10<sup>5</sup></code></li>
//	<li><code>s</code> 和 <code>t</code> 由英文字母组成</li>
//</ul>
//
//<p> </p>
//<strong>进阶：</strong>你能设计一个在 <code>o(n)</code> 时间内解决此问题的算法吗？<div><div>Related Topics</div><div><li>哈希表</li><li>字符串</li><li>滑动窗口</li></div></div><br><div><li>👍 1890</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * 最小覆盖子串
 * @author DY Rising
 * @date 2022-05-23 17:09:20
 */
public class P76_MinimumWindowSubstring{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P76_MinimumWindowSubstring().new Solution();
        System.out.println(solution.minWindow("cabefgecdaecf", "cae"));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";
        if (s.equals(t)) return t;
        char[] source = s.toCharArray();
        Map<Character, Integer> target = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            if (target.get(c) == null) {
                target.put(c, 1);
            } else {
                target.put(c, target.get(c) + 1);
            }
        }
        int leftIndex = 0, rightIndex = 0;
        //开始滑动窗口
        String minStr = "";
        Map<Character, Integer> temp = new HashMap<>();
        boolean addFlag = true;
        while (rightIndex < source.length && leftIndex <= rightIndex) {
            if (addFlag) {
                if (temp.get(source[rightIndex]) != null) {
                    temp.put(source[rightIndex], temp.get(source[rightIndex]) + 1);
                } else {
                    temp.put(source[rightIndex], 1);
                }
            }
            //对比
            if (check(target, temp)) {
                if (minStr.length() == 0 || minStr.length() > rightIndex - leftIndex +1) {
                    minStr = s.substring(leftIndex,  rightIndex + 1);
                }
                temp.put(source[leftIndex], temp.get(source[leftIndex]) - 1);
                leftIndex ++;addFlag = false;
            } else {
                rightIndex++; addFlag = true;
            }
        }

        return minStr;
    }

    public boolean check(Map<Character, Integer> target, Map<Character, Integer> temp) {
        for (Map.Entry<Character, Integer> characterIntegerEntry : target.entrySet()) {
            if (temp.get(characterIntegerEntry.getKey()) == null || temp.get(characterIntegerEntry.getKey())  < characterIntegerEntry.getValue()) return false;
        }
        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
